(A) Field of the Invention
The invention relates to an array of quantum bits (qubits) commonly known as a quantum computer. More specifically, it relates to methods for translating an input data-set into a sequence of operations that can be used to manipulate said array. The invention also relates to classical probabilistic networks (classical Bayesian nets) and their quantum counterparts.
(B) Description of Related Art
This invention deals with Quantum Computing. A quantum computer is an array of quantum bits (qubits) together with some hardware for manipulating these qubits. Quantum computers with several hundred qubits have not been built yet. However, once they are built, it is expected that they will perform certain calculations much faster that classical computers. A quantum computer can follow a sequence of elementary operations. The operations are elementary in the sense that they act on only a few qubits (usually 1, 2 or 3) at a time. Henceforth, we will sometimes refer to sequences as products and to operations as operators, instructions, steps or gates. Furthermore, we will abbreviate the phrase “sequence of elementary operations” by “SEO”. SEOs are often represented as qubit circuits. In the quantum computing literature, the term “quantum algorithm” usually means a SEO for quantum computers for performing a desired calculation. Some quantum algorithms have become standard, such as those due to Deutsch-Jozsa, Shor and Grover. For a detailed discussion of quantum computing, see the books Gru99: J. Gruska, Quantum Computing, (Osborne McGraw-Hill, 1999), and NieChu00: M. Nielsen, I. Chuang, Quantum Computation and Quantum Information, (Cambridge University Press, 2000). Also, one can find on the Internet some excellent, free introductions to quantum computing.
This invention also deals with Classical Bayesian (CB) and Quantum Bayesian (QB) nets. (Most of the literature to date deals only with CB nets and refers to them simply as Bayesian nets (or networks), without the adjective “classical”.)
A CB net comprises a graph (i.e., a diagram) and a matrix (with probabilities as entries) associated with each node of the graph. CB nets organize large amounts of probabilistic information and represent complicated probabilistic relationships. They do this in a way that is graphical, highly intuitive, and easily scalable. From the data contained within a CB net, one can derive many other conditional probabilities. Knowing such conditional probabilities is useful in applications of Decision Theory and Artificial Intelligence, wherein inferences are made based on uncertain knowledge. CB nets have been used in many areas, including pattern recognition, speech recognition, data mining, search engines, spam filters, expert systems, medical diagnosis, computer games with AI capabilities, etc. Companies which actively support the development and deployment of CB net technology include Microsoft, Intel, Google, etc. CB nets are also used in Defense (e.g., Star Wars missile discrimination). For a detailed discussion of CB nets, see the books Jen01: Finn V. Jensen, Bayesian Networks and Decision Graphs (Springer Verlag, 2001), and Pea88: Judea Pearl, Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference (Morgan Kaufmann, Palo Alto, 1988). Also, one can find on the Internet some excellent, free introductions to CB nets.
QB nets are a generalization of CB nets to quantum mechanics. A QB net comprises a graph and a matrix (with complex numbers, called probability amplitudes or just amplitudes, as entries) associated with each node of the graph. QB nets have been proposed as a graphical method for analyzing the behavior of quantum systems, in QFogPat: U.S. Pat. No. 5,787,236 by R. R. Tucci. QB net diagrams may be viewed as an alternative to qubit circuits. For an introduction to QB nets, see QFogPat and Tuc99QIT: R. R. Tucci, “Quantum Information Theory—A Quantum Bayesian Nets Perspective”, ArXiv eprint quant-ph/9909039.
The method proposed in this invention is based on an earlier method proposed by Fredkin-Toffoli (F-T) in Tof80: T. Toffoli, Automata, Languages and Programming, 7th Coll. (Springer Verlag, 1980) pg. 632, and in EreTof82: E. Fredkin, T. Toffoli, Int. Jour. of Th. Phys. (1982) Vol. 21, pg. 219. The F-T method is used in the field of (classical) reversible computing. F-T showed how, given any binary gate ƒ (i.e., a function ƒ: {0, 1}r→{0, 1}s, for some integers r, s), one can construct another binary gate ƒ such that ƒ can be used to perform the same calculations as ƒ, but in a reversible manner. We will call ƒ a deterministic reversible extension (DRE) of ƒ. Binary gates ƒ and ƒ can be represented as binary deterministic circuits. In this patent, we show how, given any CB net KC, one can construct a QB net KQ which is a “q-embedding” of KC. (“q-” stands for “quantum-”) By running KQ on a quantum computer, one can calculate any conditional probability that one would be interested in calculating for the CB net KC. Such conditional probabilities can be calculated with classical computers; the hope is that they can be calculated much faster with a quantum computer. Our method for constructing a q-embedding for a CB net is a generalization of the F-T method for constructing a DRE of a binary deterministic circuit. Thus, we generalize their method to the embedding of any classical stochastic circuit, not just binary deterministic ones.
Grover's algorithm is a quantum algorithm proposed in GroPat: U.S. Pat. No. 6,317,766, by Lov K. Grover. Our method of embedding a CB net KC within a QB net KQ can sometimes be used in combination with Grover's algorithm to great advantage. In certain cases, the target states that we wish to detect have probabilities that are too small to be measurable by running KQ on a quantum computer. However, we will show that sometimes one can construct a new QB net, call it KQ′, that magnifies to measurable values the target probabilities that were unmeasurable using KQ alone. We will refer to KQ′ as Grover's Microscope for KQ, because KQ′ is closely related to Grover's algorithm, and it magnifies some of the probabilities found with KQ.
The independent claims of GroPat are 1 and 12. Claim 1 of GroPat refers to an “arrangement”, presumably meaning quantum hardware such as a quantum computer. The claims of the present patent that pertain to Grover's algorithm require a classical computer that generates a sequence of operations; they do not require the actual application of said sequence of operations to a quantum computer. Claim 12 of GroPat refers to “A method for moving a quantum mechanical physical system which exists in a superposition of a plurality of states”. Again, this seems to require quantum hardware to be manipulated according to the method. Even if it were judged that an embodiment of claim 12 of GroPat did not require quantum hardware, the present patent claims a Grover-like algorithm only if used as a post-processor to a special, classical computer program of which a preferred embodiment called “Q-Embedder” is described below.
A quantum compiler is a computer program that one runs on classical computers. It can “compile” a unitary matrix; i.e., it can express a unitary matrix as a SEO that a quantum computer can follow. An early type of quantum compiler is discussed in Bar95: A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. H. Smolin, H. Weinfurter, ArXiv eprint quant-ph/9503016. A different type of quantum compiler is discussed in QbtrPat: U.S. Pat. No. 6,456,994 B1, by R. R. Tucci, and in Tuc99Qbtr: R. R. Tucci, “A Rudimentary Quantum Compiler (2nd ed.)”, ArXiv eprint quant-ph/9902062.
To run a QB net on a quantum computer, as is proposed in this invention, we need to translate the QB net into an equivalent SEO. This can be done with the help of a quantum compiler. A possible method of accomplishing this task is discussed in QbtrPat and in Tuc98: R. R. Tucci, “How to Compile a Quantum Bayesian Net”, ArXiv eprint quant-ph/9805016. Thus, the method of this invention promises to be fertile ground for the use of quantum compilers.
A precursor to this invention was first published in TucV1: R. R. Tucci, “Quantum Computer as an Inference Engine”, ArXiv eprint quant-ph/0004028 Version 1, submitted on 6 Apr. 2000. After TucV1 was published, Tucci realized that the method of TucV1 was flawed in some important respects. A new method, which is a substantial modification and correction of the method of TucV1, was published by Tucci in TucV2: R. R. Tucci, “Quantum Computer as a Probabilistic Inference Engine”, ArXiv eprint quant-ph/0004028 Version 2, submitted on 19 Apr. 2004. We emphasize that TucV1 is now considered obsolete and flawed by Tucci. On the other hand, Tucci currently views TucV2 as essentially correct and in agreement with this invention. TucV1 and TucV2 differ as follows. Contrary to TucV2, TucV1 does not q-embed the root nodes of the CB net that it is trying to q-embed. More importantly, Section 6.3 of TucV1 incorrectly claims that calculating a conditional probability for a CB net KC using its q-embedding KQ requires measurements of all internal nodes of KQ. TucV2 shows that only some of the external nodes of KQ need to be measured.
JaePat: U.S. Pat. No. 6,675,154, by G. S. Jaeger, proposes the use of a quantum computer for performing Fuzzy Logic. (Fuzzy Logic is a field that started with the paper Zad65: Lotfi Zadeh, “Fuzzy Sets”, Information and Control Vol 8 (1965) pgs. 338-353). Although it might at first appear that there is some overlap between the claims of JaePat and those of the present patent, careful reflection shows that this is not the case. Indeed, the independent claims of JaePat are 1, 2, 6 and 11. Claim 1 of JaePat requires the use of F1: “at least one fuzzy proposition”. Claim 2 of JaePat requires the use of F2: “fuzzy logic operations”. Claims 6 and 11 both require “fuzzy control”, which presumably requires F1 or F2. The claims of the present patent do not require F1 or F2. It is also of interest to note that many scientists and engineers are highly critical of Fuzzy Logic, and consider Bayesian Nets a far better method for dealing with situations involving uncertain knowledge.
To summarize, the present invention has the following advantages over prior art:                It merges ideas from various subjects (quantum computers, CB nets, QB nets, quantum compilers and Grover's algorithm) in a new way.        It generalizes ideas of F-T used in classical reversible computing.        It gives a method for performing CB net calculations on a quantum computer. Such calculations can be done on a classical computer. The hope is that they can be done much faster on a quantum computer.        It uses ideas from TucV2, and avoids mistakes of TucV1. TucV1 and TucV2 were both written by the inventor of this patent.        It shuns ideas from Fuzzy Logic in favor of Bayesian nets.        